/**
 * describe:
 *
 * @author chaP
 * @date 2019/03/31
 */
package CodingTest.AC20190330;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 题目描述
 给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，
 那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个：
 {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}，
 {2,3,4,2,6,[2,5,1]}。
 */
public class maxInWindows {
    //方法一：
    public ArrayList<Integer> maxInWindows(int[] num, int size){
        if(size > num.length || size == 0) return new ArrayList();
        ArrayList<Integer> res = new ArrayList<Integer>();
        int index = size-1;
        int temp[] = new int[size];
        while(index < num.length){
            temp = Arrays.copyOfRange(num,index-size+1,index+1);
            Arrays.sort(temp);
            res.add(temp[size-1]);
            index ++;
        }
        return res;
    }
//    方法二:
    public ArrayList<Integer> maxInWindows1(int[] num,int size) {
        if (num == null || num.length == 0 || num.length < size || size <= 0)
            return new ArrayList<>();
        ArrayList<Integer> result = new ArrayList<>();
        //双端队列，用来记录每个窗口的最大值下标
        LinkedList<Integer> q = new LinkedList<Integer>();
        int index = 0;
        for(int i =0;i<size-1;i++){
            while(!q.isEmpty() && num[i]>num[q.getLast()]){
                q.removeLast();
            }
            q.addLast(i);
        }
        for(int i =size -1;i<num.length;i++){
            while(!q.isEmpty() && num[i]>num[q.getLast()]){
                q.removeLast();
            }
            q.addLast(i);
            if(i-q.getFirst()+1>size){
                q.removeFirst();
            }
            result.add(num[q.getFirst()]);
        }
        return result;
    }


    public static void main(String[] args) {
        int[] num = {2,3,4,2,6,2,5,1};
        int size = 3;
        maxInWindows ma = new maxInWindows();
        System.out.println(ma.maxInWindows1(num,size));
    }

}
